package com.cjm.algorithm.dp;

public class Ti518 {
    public static void main(String[] args) {
        Ti518 ti518 = new Ti518();
        ti518.change(5, new int[]{1, 2, 5});
        ti518.change1(5, new int[]{1, 2, 5});
    }

    /**
     * 先背包， 后物品
     * <img src="https://obsidian-png.oss-cn-shenzhen.aliyuncs.com/pic2024/20240413143725.png" />
     * @param amount
     * @param coins
     * @return
     */
    public int change1(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i <= amount; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < coins.length && i >= coins[j]; j++) {
                int coin = coins[j];
                dp[i] += dp[i - coin];
                sb.append("coin=").append(coin).append(";i=").append(i).append(";dp[i]=").append(dp[i]).append("  ");
            }
            System.err.println(sb.toString());
        }

        return dp[amount];
    }

    /**
     * 先物品， 后背包
     * <img src="https://obsidian-png.oss-cn-shenzhen.aliyuncs.com/pic2024/20240413145129.png" />
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            StringBuilder sb = new StringBuilder();
            int coin = coins[i];
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
                sb.append("coin=").append(coin).append(";j=").append(j).append(";dp[j]=").append(dp[j]).append("  ");
            }
            System.err.println(sb.toString());
        }

        return dp[amount];
    }
}
